googologywikiaorg-20200223-history
Forum:I can't understand w 1^CK :(
Please give me some concrete \omega_1^{CK}n 's and O's. The abstract explanation did not make me understand. --Nayuta Ito (talk) 23:30, February 13, 2016 (UTC) :There is no such thing as \(\omega_1^{CK}n\), because nobody has developed such a fundamental sequence. You can come up with one, but it wouldn't be very useful on its own. A useful definition of \(f_{\omega_1^{CK}}\) would require a built-up fundamental sequence system for all recursive ordinals. Nobody's ever done that. That's why LittlePeng9 and I strongly advise against writing "comparable to \(f_{\omega_1^{CK}}\)" — it's an unsolved problem! :Kleene's O is an ordinal notation that maps a subset of the nonnegative integers to all recursive ordinals. For every recursive ordinal \(\alpha\), there exists a nonnegative integer \(n\) such that \(\mathcal{O}(n) = \alpha\). So if you list out \(\mathcal{O}(0),\mathcal{O}(1),\mathcal{O}(2),\ldots\), your list will contain all recursive ordinals. (Most ordinals will be represented multiple times in the list, and not all \(\mathcal{O}(n)\) are defined -- but what's important is that you have a complete list.) If you have a more specific question on the definition of Kleene's O, feel free to ask. -- ve 01:03, February 14, 2016 (UTC) ::So are the specific values of O like this?: \(\mathcal{O}(0)=0, \mathcal{O}(1)=1, \mathcal{O}(2)=2, \mathcal{O}(4)=3, \mathcal{O}(16)=4\cdots\) And I don't understand the 3*5^i part and how Turing machines are related to.--Nayuta Ito (talk) 06:02, February 14, 2016 (UTC) ::And, can you make a list with some specific numbers? Are examples for 2^^i above correct?--Nayuta Ito (talk) 08:33, February 14, 2016 (UTC) :::Your examples are correct. However, every example beyond that point strongly depends on the choice of the ordering of Turing machines. Let's fix some ordering for now. No matter what ordering this is, there is a number \(n\) such that \(n\)th Turing machine in this ordering computes function \(f(i)=2\uparrow\uparrow(i+1)\). But recall that \(\mathcal O(2\uparrow\uparrow(i+1))=i\) and so limit of \(\mathcal O(f(i))\) is \(\omega\). This means precisely that \(\mathcal O(3\cdot 5^n)=\omega\). Next, \(\mathcal O(2^{3\cdot 5^n})=\omega+1,\mathcal O(2^{2^{3\cdot 5^n}})=\omega+2\) and so on (I hope this is clear). Then, there is a number \(m\) such that \(m\)th Turing machine computes function \(g(i)=2^{\dots^{2^{3\cdot 5^n}}}\). Now, limit of \(\mathcal O(g(i))\) is \(\omega+\omega\), so this tells us that \(\mathcal O(3\cdot 5^m)=\omega+\omega\). :::Hopefully this example makes some things clearer. LittlePeng9 (talk) 08:56, February 14, 2016 (UTC) ::::I understand. O requires the map from a program to a number, and O itself goes faster than any computable functions. --Nayuta Ito (talk) 10:35, February 14, 2016 (UTC) :::::\(\mathcal O\) isn't a function from natural numbers to natural numbers, let alone it's not defined for all natural numbers. Hence it doesn't make any sense to speak of it being faster than computable functions. LittlePeng9 (talk) 10:41, February 14, 2016 (UTC) :::::You could say that for any computable function \(g(n)\), exists m such that \(f_{\mathcal{O}(m)}(m) > g(m)\). You can't talk about "eventually dominating", since not only is \(\mathcal O\)\((n)\) not defined for all \(n\), it "jumps" up and down: \(\mathcal O\)\((2\uparrow \uparrow \uparrow \uparrow 5)\) is a natural number (it is equal to 2^^n for some n), but it's quite clear that it takes way less than 2^^^^5 states to make a Turing machine that computes 2^^i+1, so we have \(\mathcal{O}(3\cdot 5^n)\) for some n much smaller than 2^^^^4 equal to \(\omega\). Maybe called Googology Noob (talk) 17:02, February 14, 2016 (UTC) ::::::Due to lack of specification of fundamental sequences \(f_{\mathcal{O}(m)}(m)\) is not well-defined for great majority of \(m\). Even if you did specify them, it's far from clear why your claim should be true. LittlePeng9 (talk) 19:15, February 14, 2016 (UTC) :::::::Given a fundamental sequence, I do not see why this is not true. Do you agree with me that for any computable function \(g(n)\), we have a recursive ordinal \(\alpha\) such that \(f_{\alpha}(n) >^*g(n)\) (because otherwise \(g(n)\) would dominate all computable functions and be a computable function itself)? Because Kleene's \(\mathcal O\) gives all recursive ordinals, we know that there will be an \(m\) such that \(\mathcal O (m)\) produces a recursive ordinal \(\alpha\) such that \(f_{\alpha}(n) >^* g(n)\). In fact, we have an infinite number of such \(m\): \(\mathcal O (2\uparrow\uparrow m)\) is trivially larger. Maybe called Googology Noob (talk) 13:06, February 15, 2016 (UTC) ::::::::No, I don't agree with your first claim, because I don't see why your parenthetical explanation is true. The scenario in which there are fundamental sequences for all recursive ordinals and yet functions \(f_\alpha\) don't exhaust all recursive growth rates is conceivable for me, and it's certainly a nontrivial thing to prove that some choice of FSs makes FGH exhaust growth rates. LittlePeng9 (talk) 15:26, February 15, 2016 (UTC) To save time I will try to clear up as many possible misconceptions about O as possible: * \(\mathcal O\) is a partial, nonmonotonic function. For instance, \(\mathcal O(n)\) is undefined if n is a nonzero multiple of 7. * If \(\alpha\) is a recursive ordinal, there exists a nonnegative integer \(m\) such that \(\mathcal O(m) = \alpha\). For all transfinite \(\alpha\), \(m\) is not unique and there are infinitely many \(m\) that satisfy this property. * \(\mathcal O\) requires us to define an ordering of all partial recursive functions \(f_0, f_1, f_2, \ldots\). The exact ordering doesn't matter, but it must contain all partial recursive functions. (EDIT: LittlePeng pointed out to me that the ordering has to be recursive. That is, there has to be a Turing machine that computes \(f_m(n)\). If that seems impossible to you, look up "universal Turing machine.") You can construct such an ordering by lexicographically ordering all Turing machines. Set theorists are generally not concerned with the details of how this ordering is done. * \(\mathcal O(0) = 0\). For finite \(n\), \(\mathcal O(2 \uparrow\uparrow n) = n + 1\). * If you want to find a value of \(m\) such that \(\mathcal O(m) = \omega\), construct a Turing machine with associated partial function \(f\) such that \(f(0) = 0\) and \(f(n + 1) = 2 \uparrow\uparrow n\) for nonnegative \(n\). Then find the index \(i\) of that Turing machine in the selected partial ordering. Then \(\mathcal O(i) = \omega\). * Don't bother asking what the smallest value of \(m\) is such that \(\mathcal O(m) = \alpha\). There is no algorithm that does that for arbitrary \(\alpha\). You might be able to solve that problem for small \(\alpha\), but it will get increasingly harder. Even finding the minimal solution to \(\mathcal O(m) = \omega\) seems very difficult, and I don't see the value in solving that problem anyway. * In general the specific values of O(m) aren't that important! What's more important is that there IS an ordinal notation that describes all recursive ordinals. -- ve 19:45, February 14, 2016 (UTC) :I've written a blog post that describes a system analogous to Kleene's O. It might be easier to understand for people experienced with programming. -- ve 20:42, February 14, 2016 (UTC) ::By the way, could we not define the fundamental sequence for \(\omega_1^{CK}\) like this: \(\omega_1^{CK} n = \text{max} \lbrace \mathcal{O}(m) : 2 \uparrow \uparrow n \geq m \rbrace\) Maybe called Googology Noob (talk) 11:57, February 27, 2016 (UTC) :::We could. We also could define it in 23387614307834 different ways. LittlePeng9 (talk) 13:24, February 27, 2016 (UTC) ::::What I meant was, why don't we adopt that as the fundamental sequence for \(\omega_1^{CK}\)? Maybe called Googology Noob (talk) 17:50, February 27, 2016 (UTC) :::::I have at least two reasons why I wouldn't want to adopt it as a "standard" fundamental sequence. :::::# Kleene's \(\mathcal O\), and hence also your suggested definition of FS, depends on the enumeration of partial recursive functions, and there is no standard enumeration. Because of that, many different enumerations would lead to many different Kleene's \(\mathcal O\)s and fundamental sequences for \(\omega_1^\text{CK}\), without any specific indication as to which ones are "better" than the others. :::::# Since the primary goal (at least for us as googologists) of specifying fundamental sequences is to use them with FGH, the fact that we don't have even a slightest clue how FGH works with this definition of FSes for \(\omega_1^\text{CK}\) (similar definition of FS for smaller limit ordinals could be devised, so I don't consider that problem here). Of course one could argue that we don't know how FGH would define for most other definitions of FSes, but my reply to this would be that I take it as an argument to not take any definition of the fundamental sequence of \(\omega_1^\text{CK}\). :::::One could also argue that using Kleene's \(\mathcal O\) is not a natural way of constructing fundamental sequences, but I've decided to not make it into the third reason because "naturalness" is too subjective matter. LittlePeng9 (talk) 19:41, February 27, 2016 (UTC) :::::A single fundamental sequence for CK is not useful. You need fundamental sequences for all ordinals less than CK to use it in an ordinal hierarchy. Not only that, but the FS system must not be degenerate. -- ve 07:16, February 29, 2016 (UTC) ::::::We can define fundamental sequences for all limit ordinals less than \(\omega_1^{CK}\) by \(\alpha n = \text{max} \lbrace \mathcal{O}(m) < \alpha : 2 \uparrow \uparrow n \geq m \rbrace\). We can insure that this gives an increasing FGH hierarchy by modifying the limit rule of FGH to \(F_\alpha (n) = \sup_{m \le n} \lbrace F_{\alpham}(n) \rbrace\). So we can define an explicit increasing hierarchy of FGH up to \(\omega_1^{CK}\). Deedlit11 (talk) 20:46, February 29, 2016 (UTC) :::::::Nice, that seems to work. But now we encounter a different problem -- what do we do with this? I don't see how we can prove anything about the growth rate of \(f_\alpha\) for most \(\alpha\). -- ve 06:14, March 1, 2016 (UTC)